1. Field of the Invention
This invention relates in general to a method and apparatus for controlling Internet Protocol flows, and more particularly to a method and apparatus for providing fair traffic scheduling among aggregated IP flows.
2. Description of Related Art
Today, an organization's computer network has become its circulatory system. Organizations have combined desktop work stations, servers, and hosts into Local Area Network (LAN) communities. These Local Area Networks have been connected to other Local Area Networks and to Wide Area Networks (WANs). It has become a necessity of day-to-day operation that pairs of systems must be able to communicate when they need to, without regard to where they may be located in the network.
During the early years of network computing, proprietary networking protocols were the standard. However, the development of the Open Systems Interconnection Reference Model introduced by the International Organization for Standardization (ISO) has led to an impressive degree of interworking, which generally allows end-user applications to work very well between systems in a network. Implementations are based on written standards that have been made available by volunteers from dozens of computer vendors, hardware component vendors and independent software companies.
During the last decade, LANs have been proliferating. This has created a recurring problem of how to minimize congestion and optimize throughput that must be solved by network managers. An early solution was to simply divide Local Area Networks into multiple smaller networks serving smaller populations. These segments were connected by bridges to form a single Local Area Network with traffic being segregated locally to each segment.
The evolution of new network types and Wide Area Networks created a need for routers. Routers added filtering and firewalling capability to provide more control over broadcast domains, limit broadcast traffic and enhance security. A router is able to chose the best path through the network due to embedded intelligence. This added intelligence also allowed routers to build redundant paths to destinations when possible. Nevertheless, the added complexity of best path selection capability accorded by the embedded intelligence increased the port cost of routers and caused substantial latency overhead. Shared-media networks comprising distributed client/server data traffic, expanded user populations and more complex applications gave birth to new bandwidth bottlenecks. Such congestion produced unpredictable network response times, the inability to support the delay-sensitive applications and higher network failure rates.
Networks and protocols in use today have been designed to operate using connection-less transmission technology based on global addressing. The most popular protocol of this type is the Internet Protocol (IP).
An internet is a set of networks connected by gateways, which are sometimes referred to as routers. The Internet Protocol is a network layer protocol that routes data across an internet. The Internet Protocol was designed to accommodate the use of host and routers built by different vendors, encompass a growing variety of growing network types, enable the network to grow without interrupting servers, and support higher-layer of session and message-oriented services. The IP network layer allows integration of Local Area Network "islands". Still, graphics and multimedia content are putting ore demand on the performance of such networks. As the umber of users increases network traffic, bandwidth becomes increasingly problematic. While the Internet continues to grow, so does the intranet as more and more private enterprise networks are being based on the Internet Protocol.
IP traffic is carried over various data link layers (L2) and transmission media. IP consists of flows, which are sequences of interrelated packets that are sent from a source to a destination(s). Multiple IP flows can be conveyed over a single data link.
In cases where logical data link layer connections can be used, two possibilities exist for carrying IP flows over data link layer connections. A data link layer (L2) connection can either be dedicated for a single IP flow or, alternatively, several flows can be multiplexed into one connection. If these different types of L2 connections have the same L2 traffic class, the connections are competing for the same network resources. If both of these methods of utilizing L2 connections are used in the network at the same time and, as is generally the case, fairness between users of the IP network (i.e., fairness among aggregated IP flows in an IP network) has to be guaranteed. In general, the IP flows which have the identical level of IP Quality of Service should get equal treatment in the network. However, a simple scheduling algorithm where one L2 data unit is taken from each queue, as currently implemented in the art, in turns favors connections that carry only one or few IP flows. Therefore, more sophisticated approaches have been tried.
For example, an approach of measuring carried traffic over a particular connection in terms of bytes or frames transferred over an L2 connection is straightforward. However, fair scheduling cannot be based solely on traffic volume. Otherwise, bandwidth intensive flows would disproportionately dominate the traffic flow at the cost of the other flows. To provide fairness at the IP level, information is needed about the number of flows using each connection. Unfortunately, traffic monitoring cannot be done at the data link layer as interpretation of the traffic is based on the information carried in the higher level protocol data units. Nevertheless, there are three basic methods that can used for obtaining the necessary information on flows.
The first method, Out-of-Band notification, uses a separate IP level protocol to inform network elements along the path of an L2 connection on the approximate number of users. This information is more naturally generated by the edge devices. Out-of-Band notification can also be given to a network element via a network management system through an operator's initiative, which is further distributed among network elements by the separate IP level protocol. However, a solution where network management configures these values to each network element is not scaleable to large networks.
The second method is packet snooping. Packet snooping involves intermediate network elements periodically analyzing the traffic flow to get an idea about how many flows utilize each L2 connection.
The third method is an implicit method, e.g., different logical identifier ranges are used for different aggregation levels. When setting up an L2 connection, e.g., tag switching or other IP switching methods like Ipsilon flow management schemes, the flow granularity is taken into account when deciding the service level. If the L2 connection identifier is associated with an IP network address, then it is likely that more flows will use that L2 connection. Also, the address can provide an indication of the size of the target network. With IPv4 network classification, for example, this implementation is straightforward.
Still, using a separate IP level protocol requires standardization and implicit methods, although seemingly straightforward, requires careful configuration between adjacent network elements. However, packet snooping can be implemented individually by each network element.
It can be seen then that there is a need for a method and apparatus that provides for fair traffic scheduling. It can also be seen that there is a need for a fair traffic scheduling method and apparatus that can be implemented by each network element.